package nz.ac.massey.cs.domain;

import java.util.ArrayList;

import nz.ac.massey.cs.utils.CellType;

// this class implements solver which can take in a sudoku object and solve it
public class Solver implements ISolver{

	private ISudoku sudoku;
	int x = 0;
	int y = 0;
	private ArrayList<Cell> criticalCellList;
	private Boolean isFirstRun = true;

	public Solver() {
		this.criticalCellList = new ArrayList<Cell>();
	}

	public Solver(ISudoku sudoku) {
		this.sudoku = sudoku;
		this.criticalCellList = new ArrayList<Cell>();
	} 


	public void setSudoku(ISudoku sudoku) {
		this.sudoku = sudoku;
	}

	public ISudoku getSudoku() {
		return sudoku;
	} 

	/*
	 * for back tracking until a value can be found for a cell
	 */
	private Cell backTrackTillChange(int x, int y)
	{
		Cell cellToReduce = sudoku.getCellByIndex(y, x);
		if(cellToReduce.getType().equals(CellType.VARIABLE))
		{
			Boolean viable = true; // used for telling weather or not the current value for a cell is acceptable for all its constraints
			Boolean upto = false; // boolean for telling when the value in the possible value list has been found
			Boolean done = false ; 
			for(int i =0; i < cellToReduce.getPossibleValueList().size() ; i++)
			{
				String value = cellToReduce.getPossibleValueList().get(i);
				if(done)
				{
					if(upto)
					{
						cellToReduce.setValue(value);
						for(IConstraint con:cellToReduce.getConstraints())
						{
							if(!con.isViolated() && viable)
							{
								viable = true;
							}
							else
							{
								viable = false;
							}
						}
						if(viable)
						{
							this.x = x;
							this.y = y;
							System.out.print(x+ "  " + y);
							return cellToReduce;
						}
						viable = true;
					}
				}
				else
				{
					if(value != cellToReduce.getValue() && !upto)
					{
						continue;
					}
					else
					{
						upto = true;
						done = true;
						value = cellToReduce.getPossibleValueList().get(i);
					}
				}
			}
			cellToReduce.setValue("");
		}

		x--;
		if(y < 0 && x < 0)
		{
			return null; // not solvable
		}
		else if(x < 0)
		{
			x = sudoku.getRowSize() - 1;
			y--;
		}

		return backTrackTillChange(x, y); 
	}

	public Cell solveNext() {

		// first time solve Sudoku, initialize possible values of cell 
		if ( true == isFirstRun ) {
			System.out.println("first time run");
			updatePossibleValuesForCell();
			findCriticalCell();
		}

		if ( this.criticalCellList.size() > 0 ){
			for ( Cell criticalCell:this.criticalCellList ){
				criticalCell.setValue(criticalCell.getPossibleValueList().get(0));
				criticalCell.setType(CellType.FIXED);
				System.out.println("filled "+criticalCell.toString()+"cell type:"+criticalCell.getType());
				this.criticalCellList.remove(criticalCell);
				updatePossibleValuesForCell();
				findCriticalCell();
				return criticalCell;
			}
		}
		else {
			isFirstRun = false;
		}

		// other wise revert to brute force
		Cell cellToReduce = sudoku.getCellByIndex(y, x);

		while(cellToReduce.getValue() != "" || cellToReduce.getType() != CellType.VARIABLE)
		{

			x++;
			if(y >= sudoku.getColSize() -1 && x >= sudoku.getRowSize())
			{
				System.out.println("we win");
				return null;
				//					y = 0;
				//					x=0;
			}
			else
			{
				if(x >= sudoku.getRowSize())
				{
					y++;
					x = 0;
				}
			}
			cellToReduce = sudoku.getCellByIndex(y, x);
		}

		Boolean hasValue = false;
		Boolean viable = true;
		for(String value:cellToReduce.getPossibleValueList())
		{

			cellToReduce.setValue(value);
			for(IConstraint con:cellToReduce.getConstraints())
			{
				if(!con.isViolated() && viable)
				{
					viable = true;
				}
				else
				{
					viable = false;
				}
			}
			if(viable)
			{
				return cellToReduce;
			}
			viable = true;
		}
		cellToReduce.setValue("");
		do
		{
			x--;
			if(y < 0 && x < 0)
			{
				return null; // not solvable
			}
			else if(x < 0)
			{
				x = sudoku.getRowSize() - 1;
				y--;
			}
		}while(sudoku.getCellByIndex(y, x).getType() != CellType.VARIABLE); 

		return backTrackTillChange(x, y);
	}

	private void updatePossibleValuesForCell(){
		Cell[][] cellMatrix = this.sudoku.getCells();
		for (int i=0; i<this.sudoku.getRowSize(); i++) {
			for (int j=0; j<this.sudoku.getColSize(); j++){

				if ( CellType.VARIABLE != cellMatrix[i][j].getType() 
						|| cellMatrix[i][j].getType() == CellType.FIXED) {
					continue;
				}
				ArrayList<String> obsoleteValueList = new ArrayList<String>();
				for(String value:cellMatrix[i][j].getPossibleValueList())
				{
					cellMatrix[i][j].setValue(value);
					for(IConstraint con:cellMatrix[i][j].getConstraints())
					{
						if(con.isViolated())
						{
							obsoleteValueList.add(cellMatrix[i][j].getValue());
						}
					}				
				}
				//ArrayList<String> stuffToRemove = new ArrayList<String>();

				for(String value:cellMatrix[i][j].getPossibleValueList())
				{
					cellMatrix[i][j].setValue(value);
					if(isNotPossibleElseWhere(cellMatrix[i][j]))
					{
						for(String obsoultevalue:cellMatrix[i][j].getPossibleValueList())
						{
							if(obsoultevalue != value)
							{
								obsoleteValueList.add(obsoultevalue);
							}
						}
					}
				}

				for(String value:obsoleteValueList)
				{
					cellMatrix[i][j].removePossibleValue(value);
				}

				cellMatrix[i][j].setValue("");
				//					System.out.println(cellMatrix[i][j].toString()+"get possible values:"+cellMatrix[i][j].getPossibleValueList());
			}
		}
		//			System.out.println("finish initPossibleValuesForCell");
	}

	public boolean isCellInCriticalList(Cell tempCell) {
		if ( 0 == this.criticalCellList.size() ){
			return false;
		}
		for (Cell criticalCell:this.criticalCellList ){
			if (tempCell.getRowIdx() == criticalCell.getRowIdx() 
					&& tempCell.getColIdx() == criticalCell.getColIdx() ) {
				return true;
			}
		}
		return true;
	}

	public void findCriticalCell() {
		Cell[][] cellMatrix = this.sudoku.getCells();
		for (int i=0; i<this.sudoku.getRowSize(); i++){
			for (int j=0; j<this.sudoku.getColSize(); j++) {
				if ( cellMatrix[i][j].getType() == CellType.VARIABLE ) {
					if ( 1 == cellMatrix[i][j].getPossibleValueList().size() ){
						if (isCellInCriticalList(cellMatrix[i][j])) {
							continue;
						}
						this.criticalCellList.add(cellMatrix[i][j]);
						//							System.out.println("get a cell with unique value"+cellMatrix[i][j].toString());
					}
				}
			}
		}
	}


	private boolean isNotPossibleElseWhere(Cell cell)
	{
		for(IConstraint con:cell.getConstraints())
		{
			if(isNotPossibleInConstraint(cell, con))
			{
				return true;
			}
		}
		return false;
	}

	private boolean isNotPossibleInConstraint(Cell cell,IConstraint con)
	{
		for(Cell test:con.getCells())
		{
			if(test.getPossibleValueList().contains(cell.getValue()))
			{
				return false;
			}
		}
		return true;
	}
}
